package 常见算法.分治之快速排序;

/**
 * @Date 2024/6/13 20:13
 * @description: 快排之颜色分类
 * .            https://leetcode.cn/problems/sort-colors/
 * @Author LittleNight
 */
public class likou75 {

    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = -1, right = n;
        for(int i = 0; i < right; ) {
            if(nums[i] == 0) {
                // left 标记0区域的最右的一个位置
                swap2(++left, i++, nums);
            } else if(nums[i] == 1) {
                // 中间的区域直接跳过
                i++;
            }else {
                // right 标记2区域的最左侧位置
                // 注意这个位置没有 i++
                swap2(--right, i, nums);
            }
        }
    }
    private void swap2(int left, int right, int[] nums) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}
